/*******************************************************************************
filename      SCVector.h
author        Craig Williams

Brief Description:
  CVector with sorting capabilities.

  This vector does not have to be sorted.

  functions:
    push_back()  - Adds a new elment to the end of the vector. This will break
                     the sort state.
    erase()      - Erases the specified element. If the vector is sorted, all
                     elements after the specified element will be shifted over.
                     Otherwise, the CVector erase is performed.
    insert()     - If the vector is sorted, a binary search is performed to
                     find the insertion spot, followed by shifting over all
                     the elements after that spot. If it is not sorted,
                     push_back() is used.
    sroted()     - Is the vector sorted?
    sort()       - Sorts the vector. If the vector is already sorted, this does
                     nothing. This uses quick sort.
    force_sort() - Forces the vector to sort. This is useful if one of the
                     elements changed within the vector that breaks the sort
                     order.

  search function: Linear Search if not sorted, binary otherwise.
    find_index() - Finds the index of the specified element in the vector.
                     ~0 if it is not found.
    find()       - Finds the specified element. NULL if not found.
    find_first() - Finds the first copy of the specified element.
                     NULL if not found.
    find_all()   - Finds all copies of the specified element.
*******************************************************************************/
#ifndef SCVECTOR_H
#define SCVECTOR_H

#include "CVector.h"

template<typename T> bool DefLess(const T &l, const T &r){return l <  r;}

template<typename T>
class SCVector : public CVector<T>
{
  public:
    SCVector(int initsize = 10, float growth = 1.5f,
              bool (*les)(const T&, const T&) = DefLess);
    SCVector(const SCVector<T> &vec);

    SCVector &operator=(const SCVector<T> &vec);

      // Insertion/Removal of elements
    void push_back (const T &data     );
    void erase     (unsigned int index);

      // Extension: Array Sorting
    T   &insert    (const T &data); // If sorted, < of type T is used.
    bool sorted    (void) const;    // Is the array sorted?
    void sort      (void);          // Quick sort. uses <
    void force_sort(void);
    void mark_unsorted(void);

      // Accessors
    unsigned int find_index(const T &item) const;
    T   *find      (const T &item) const;
    T   *find_first(const T &item) const;
    CVector<T *> find_all(const T &item) const;

  private:
    bool (*less)  (const T &l, const T &r);

    unsigned int Sorted;  // Is the data sorted?
};

#include "SCVector.cpp"

#endif //SCVector_H
